#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int value;

	struct node* left;
	struct node* right;
}tree;

/* The problem does not assume that either of the trees
 * are binary search trees. The problem is to find if one 
 * binary tree is part of another, and neither need to be a
 * binary search tree. However, to make it easy for implementation,
 * I am re-using the insert function of a binary search tree.
 *
 * the is_sub_tree function below will work with any binary tree
 */
tree * insert (tree * root, int value)
{
	tree *node;
	if (!root) {
		node = malloc(sizeof(tree));
		node->value = value;
		node->left = node->right = NULL;
		return node;
	}

	tree *active, *prev;
	active = root;

	while (active) {

		prev = active;

		if (active->value < value)
			active = active->right;
		else if (active->value > value)
			active = active->left;
		else {
			printf ("%d element already exists\n", value);
			return root;
		}
	}

	node = malloc(sizeof(tree));
	node->value = value;
	node->left = node->right = NULL;

	if (prev->value < value)
		prev->right = node;
	else
		prev->left = node;

	return root;
}

#define TRUE 1
#define FALSE 0

int match_tree (tree *t1, tree *t2)
{
	int ret = FALSE;

	if (t1->value != t2->value)
		return FALSE;

	if (t2->left) {
		if(!t1->left)
			return FALSE;
		else {
			ret = match_tree (t1->left, t2->left);
			if (!ret)
				return FALSE;
		}
	}

	if (t2->right) {
		if(!t1->right)
			return FALSE;
		else
			return match_tree (t1->right, t2->right);
	}

	return TRUE;
}

	

int is_subtree (tree *t1, tree *t2)
{

	int ret = FALSE;

	if (!t1)
		return FALSE;
	if (!t2)
		return TRUE;

	if (t1->value == t2->value)
		return match_tree (t1, t2);

	if (t1->left) {
		ret = is_subtree (t1->left, t2);
		if (ret)
			return TRUE;
	}

	if (t1->right) {
		ret = is_subtree (t1->right, t2);
	}

	return ret;
}


int main ()
{
	tree *t1;

	t1 = insert (NULL, 4);
	t1 = insert (t1, 2);
	t1 = insert (t1, 9);
	t1 = insert (t1, 1);
	t1 = insert (t1, 3);
	t1 = insert (t1, 5);
	t1 = insert (t1, 12);

	tree *t2;

	t2 = insert (NULL, 4);
	t2 = insert (t2, 2);
	t2 = insert (t2, 9);
	t2 = insert (t2, 1);
	t2 = insert (t2, 3);

	if (is_subtree (t1, t2))
		printf ("SUBTREE\n");
	else
		printf ("Not a subtree\n");

	return 0;
}
